- Title
- The asymmetric traveling salesman problem with replenishment arcs
- Creator
- Boland, Natashia; Clarke, L. W.; Nemhauser, G. L.
- Relation
- European Journal of Operational Research Vol. 123, Issue 2, p. 408-427
- Publisher Link
- http://dx.doi.org/10.1016/S0377-2217(99)00266-0
- Publisher
- Elsevier
- Resource Type
- journal article
- Date
- 2000
- Description
- We consider a constrained asymmetric traveling salesman problem with knapsack-like constraints on subpaths of the tour. This problem arises in routing aircraft. We formulate the problem with an exponential number of variables that correspond to feasible subpaths. We study certain polyhedral aspects of the reformulation and present a branch-and-price-and-cut algorithm for solving it. We test the algorithm on both random instances and real instances that arise in the airline application.
- Subject
- optimization; traveling salesman; column generation; cut generation
- Identifier
- http://hdl.handle.net/1959.13/939495
- Identifier
- uon:12820
- Identifier
- ISSN:0377-2217
- Language
- eng
- Reviewed
- Hits: 1700
- Visitors: 1952
- Downloads: 0
| Thumbnail | File | Description | Size | Format |
|---|